Date: Tue, 26 Nov 1996 18:41:10 GMT
Server: NCSA/1.5.1
Last-modified: Tue, 23 Apr 1996 04:16:24 GMT
Content-type: text/html
Content-length: 15869

<html>
<HEAD>
<TITLE>CS 60:  Principles of Computer Science</TITLE>
</HEAD>
<BODY>
URL http://www.cs.hmc.edu/~keller/cs60s96.html
(Link to <!WA0><a href = "http://www.cs.hmc.edu/~keller/cs60s96index.html">INDEX page</a>).
<center>
<H4>
<!WA1><a href = "http://www.hmc.edu/">Harvey Mudd College</a>, Spring 1996</H4>
<H2>
<!WA2><A HREF="http://www.cs.hmc.edu/index.html">Computer Science</A> 60</h2>
<h1>Principles of Computer Science</h1>
<h2>Home Page and Reference Card</h2>
</H2>
</center>
<h4>
<a name = "personnel">Course Personnel</a>
</h4>
<ul>
<li>Instructor: <!WA3><a href = "http://www.cs.hmc.edu/~keller"> Robert Keller </a>
242 Olin (4-5 p.m. MTuWTh or by appt.), keller@muddcs, x 18483
<br>
<li>Secretary: <!WA4><a href = "http://www.cs.hmc.edu/~nancy"> Nancy Mandala</a> 240 Olin (1-5 M-F)  nancy@muddcs, x 18225
<br>
<li>CS Intern (for account problems, etc.): Vacant position, please mail to help@muddcs instead.
<br>
<li>Official mascot: <!WA5><a href = "http://www.cs.hmc.edu/~keller/rex.html"><em>rex</em></a>
<br>
<li>Tutor/Graders
<ul>
<li><!WA6><a href = "http://www.cs.hmc.edu/~mdharm/">Matt Dharm</a> '98: mdharm@muddcs, x74863
<li><!WA7><a href = "http://aij.st.hmc.edu/~jlarkin">John Larkin</a> '98: jlarkin@muddcs, x73592
<li>Jeff Polakow '96: jpolakow@muddcs, x76747
</ul>
<li>Grader account: <b>mail assignments to:</b> cs60grad@muddcs.cs.hmc.edu.  
<li><b><a name = "tutor_hours">Tutor Hours:</a></b>
Here is the current schedule of when tutors will be in the terminal room,
102 Beckman:
<listing>

Mon 7-10                 Jeff Polakow
Tue 7-10                 Jeff Polakow
Wed 7-8:30               John Larkin
Thu 4-5:30 & 6:30-8:30   John Larkin
Fri 2-5                  Matt Dharm
</listing>
If you would like help but these hours do not work for you, please let me
know.
<p>
</ul>

<a name = "location">Room 102 Beckman</a>
is where the X terminals connected to our machine muddcs are.
To find it, leave the back of the lecture hall (Galileo Edwards) turn right,
then another right down the long corridor.  Proceed to the new section of
the building, then turn right.  102 is the second door on the right.

<p>
To get to my office, go back to the long corridor and keep going to 
the end.  Go right, then upstairs (you will then be in the Olin building), 
then go left, then left again, to the southeast corner of Olin.  My office
is 242, which is inside of 240.  240 is always open during business hours.
My door is usually closed to filter out noise, but don't hesitate to knock.

<P>
<h4><a name = "catalog">Catalog Description</a></h4>
Introduction to principles of computer science.  Algorithms, complexity
analysis, data structuring, data and procedural abstraction, grammars, 
correctness, logic principles, processor organization, operating system 
concepts, programming languages, basic automata theory, and theoretical 
limitations.
<P>
<b><h4><a name = "goals">Course Goals</a></h4></b>

To learn and apply basic principles of computer science, including
software construction, hardware organization, and limitations of
computers.  
<P>
<b><h4><a name = "text">Text</a></h4></b>
Robert M. Keller, <em> Principles of Computing</em>, January 1996.
Available by one-time special order for $29 (cost of reproduction)
and it is strongly recommended that you buy a copy.

The entire book is also on-line in Microsoft word on KATO, the Mac
server, in the folder KATO.HOME/Department Homes/CS/CS 60/.  It will
be thus viewable from Macs on the local network.  I will see about
getting a PC version as well.  <em>However</em>, it is <em>still</em>
recommended that you purchase the book (rather than, say getting
someone's old version) because: (1) The book has been revised
substantially since the last course offering.  (2) The book is large
(750 pages), and reading it all on the screen is apt to be tiresome
and inconvenient.  (3) The book can be taken into the exams, whereas a
Mac cannot be.

<p>
<b><h4><a name = "assumptions">Course Assumptions</a></h4></b>

Students should have had a first course in computing at the college
level (e.g. CS5).  Prior experience in C or C++ is preferred although
not essential.  Others have made it through starting with just a
knowledge of Pascal.  You should know about procedures, arrays, and
types at a minimum; if you are unfamiliar with these, please take CS5
or CS50 first.

<b><h4>"Lectures"</h4></b>

The word "lecture" below is used very loosely.  I expect that the lecture
periods will include some explanation, but will be more like a 
multilogue (set of dialogues).  You are expected to attend, ask
questions, and provide comments.

<b><h4><a name = "threads">Threads</a></h4></b>

There are essentially three interwoven "threads" in the course: The book,
the problems, and the lectures.  I try to keep them "in synch" with one
another, but active participation in all three threads is required.
Volume-wise, the book covers more material than can be discussed in the
lecture.  The lecture will cover some things not in the book.
Staying attune to what is going on in lecture will help you focus on
the areas in the book that are important as far as exam emphasis.  
The problems exercise some, but not all, of the
things discussed in the book and lecture.

<b><h4><a name = "resources">Resources</a></h4></b>

The course is planned to be interactive throughout.  We are eager to
prevent programming difficulties from consuming extraordinary time, so
please <em>ask</em> when you get stuck with such difficulties.  It is
much more efficient to <b>start early</b> on each assignment so that
you give yourself enough time to cope with the numerous contingencies
which inevitably materialize.  You can get help on-line by emailing to
cs60help@muddcs which goes to the graders/tutors and to me.  I don't
enable 'talk' because it is too slow, but I check email often.  When
you email a message, it will typically be answered to the entire class
with parts of your message embedded.  <em>If you do not want it to be
attributed to you, please so indicate in your message.</em> <p> 

By carrying problem solutions through to computer implementation, you
are showing that you understand the issues, principles, and
techniques.  I will explain to you how to work any problem, to any
level of detail, if you ask.  However, you must do so with a
sufficient time margin.  Telling me at the eleventh hour that you just
aren't getting and therefore want to drop the course is not availing
yourself of the substantial help available.

<p> You are also welcome to submit email or a note card with any
question you'd like to have answered or any point you would like
addressed before or after class, or leave it in my mailbox in 240
Olin.  Of course you are encouraged to ask such questions in class as
well.  There are many tools available on the computer itself.  Use the
'man' feature of UNIX to find what you need and to explore.  (The command 
<listing>
man <em>command</em> 
</listing>
gives information on a specific command; 
The command 
<listing>
man -k <em>topic</em> 
</listing>
lists commands relating to a specific topic.)  You can also
use the 'info' reader in GNU Emacs for certain library, language, and editor
specifics.  In emacs type 
<listing>
escape-X info
</listing>
Helpful information, examples, on-line copies of
assignments, etc. will be kept in various subdirectories of the
directory 
<listing>
<!WA8><a href = "http://www.cs.hmc.edu/~keller/cs60">/cs/cs60</a>
</listing>
on machine muddcs.  There is a web page for <!WA9><a href
= "http://www.cs.hmc.edu/~keller/rex.html"><em>rex</em></a> documentation.  Finally, the "corner
store" maxim applies: <em>If you can't find what you want, ask for
it.</em> <P> 

<b><h4><a name = "grading">Grading</a></h4></b>
There will be approximately eight assignments entailing programming.
Programming assignments help drive home key working concepts and
principles.  After the first couple of assignments, where the rex
language (one you have not likely seen) is used, the language used will
mostly be C++.  C++ is used due to its position as an emergent
industry standard and its ability to reflect both low-level computer
structure and at the same time provide high-level data and object
abstractions.  There will may be one assignment in assembly-language
programming, using a simulated computer, the ISC.  As prior exposure
to C++ varies across the class, I will hold one or more special
evening sessions for C++ if you so request.
<P>
<b><h4>Is this a "Programming Course"?</h4></b>

Although much of the course entails programming, we  consider exposure
to computer science ideas to be the important part.  The intent of the
programming assignments is to drive home these key ideas.  I am
willing to devote as much of each class period as is needed (nominally
15 minutes) to more detailed examples of programming techniques and
for specific programming questions and answers.  If this does not
appear useful on a given day, the time will be used for other
purposes.   

<p>
<b><h4><a name = "honor_code">Honor Code Standard</a></h4></b>

<em>Read this carefully:</em>
Although <em>discussion</em> of problems with others is encouraged,
programming in CS60 emphasizes individual learning rather than group
projects.  We observe the following Standard:  "You may <em>discuss</em> the
assignment with other students.  You may not
share (= give or receive)
written work of any kind, inside or outside the course".
Elaboration:  In the case of programming assignments, we consider
email, computer files, fragments of files, and printed output to be "written
work".  In developing code for a programming assignment, you can
discuss ideas with others, but discussion of ideas
must not involve wholesale examination or 
transcription of the actual working code of
others, with the exception that you may use any code explicitly
provided by the instructor. <strong>Definitely
forbidden</strong> is a form of collaboration wherein two or more students
split up an assignment, then transcribe each others' contributions,
sometimes changing names of variables, comments, formatting, etc.  
If this occurs, a failing grade is issued automatically.
If the help you get from another is significant, you should acknowledge
it on your submission.  You do not lose credit for this.
<em>If you have any doubts about whether a form of
interaction constitutes a violation of this standard, please consult
with me prior to continuing.</em>
<P>

<b><h4><a name = "grading_weights">Grading Weights</a></h4></b>
The programming assignments will constitute 50% of the grade.  The
mid-term examination will count 15% and the final 25%.  Class
attendance, participation, random quizzes, etc. will account for the
remaining 10%.  Various "practice problems" will be indicated.  In
particular, you should be able to work most ** ("two dot") problem in
the notes relating to material covered in lecture.  These do not need
to be submitted, but the exams will consist largely of problems of a
similar level, along with some perhaps a little easier or harder.
Exams are open book and emphasize conceptual understanding, rather
than memorization of fine details.  
<P>
<b><h4><a name = "late">Late Assignment Policy</a></h4></b>

Submissions are done by emailing source code to the grader,
cs60grad@muddcs, which also establishes the time of submission.
The due dates on assignments should be noted carefully.
The work of an assignment should be conducted in the week or weeks
before, not on the last day when there is no space for the necessary
thinking.  
There is an automatic, fixed, one-day grace period on all assignments.  
In other words, if the due date
states day N, then the assignment must be turned in before midnight on
day N+1 to receive any credit.  After midnight on day N+1 work you
spend on the problem is for you own edification only (which is not 
to say that it isn't worth doing or required; you just don't get
points for it then).  It is best to plan to get the assignments in
on the stated due date.
<P>
<b><h4><a name = "outline">CS 60 Topic Outline</a></h4></b>

The lectures will roughly follow this outline.  The progression is at
the rate of about two of the numbered topics below per week.  I should
say that this is what I would <em>like</em> to do.  Depending on background,
some of the topics expand to longer than allocated, with the result
that other topics get jettisoned or fall off the end.  Please keep up
on the reading without it being explicitly assigned.  The notes
generally expand on the lectures and discussions.  But the lectures
may also expand on the notes or introduce new material.  More often
than not, several threads will be interwoven in the lectures over a
period of time, in part to emphasize the commonality of concepts from
different vantage points.  Brackets below indicate where chapters in
the notes start with respect to the concepts that follow.  The outline
does not mention every topic.  The actual lectures determine points of
emphasis.
<P>
<ol>
<li>[<em>Computing by the Rules</em>]  Computation problems and models of
computation. States and transitions.  List notation.   Functional
specifications.  Computation by rewriting.
<p>

<li>Heterogeneous lists and trees.  Mutual recursion.  Anonymous
functions.     
<p>

<li>Assignment-based programs.  McCarthy's transformation.  Turing
machines.
<P>

<li>[<em>Computing on Demand</em>]  C++ review, the Polya library
(translating rex to C++)
<p>

<li>
RAM model, linear addressing principle,
arrays, pointers, L-values and R-values.
<P>

<li>[<em>Computing Grammatically</em>]  Inductive definitions, grammars,
syntax.
<P>

<li>Parsing.   Evaluation.  S expressions.
<P>

<li>[<em>Structural Computing</em>] Data structuring.  Dynamic storage
allocation.  Open- vs. Closed-list models
<P>

<li>[<em>Computing Objectively</em>]  Object-orientation and data abstraction.
C++ objects.  Inheritance.
<P>

<li>[<em>Computing Logically</em>]  Proposition logic and applications.  Gate
realizations.  Minterm expansion.  Boole/Shannon expansion.
<P>

<li>Logic simplification.  Hypercubes. Karnaugh maps.  "Don't care"
situations. 
<P>

<li>Predicate logic.   Programming in logic.  Backtracking. 
<P>

<li>Program specification, correctness, and verification.
<P>

<li><a name = "midterm">Mid-term examination</a>.  (<b>Date of Midterm: Wed. Mar. 6, during class period</b>).
<P>

<li>[<em>Complexity of computing</em>]  Runtime measures. Profiling.
Growth-rate comparisons.  Upper bounds.  "O" notation.   Examples from
sorting: Heapsort, merge sort, radix sort.
<P>

<li>Complexity (continued).  Empirical measurements.  Set abstraction examples.  Bit-vectors,
tries.
<P>

<li>[<em>Computing graphically</em>]  Directed graphs.  Graph representations,
depth- and breadth-first search.
<P>

<li>Weighted graphs.  Shortest paths.  Traveling salesman problem.
<P>

<li>[<em>Finite-State Computing</em>]  Finite-state machines.  Sequential
logic design.
<P>

<li>Regular expressions and finite-state machines.
<P>

<li>Computer components.  Registers, buses, multiplexors, etc.
<P>

<li>[<em>Computing with the Store</em>]  Stored-program computer structure.  
<P>

<li>Assembly language.
<P>

<li>[<em>Computing physically</em>]  Physical bases for computation.
<P>

<li>[<em>Computing in Parallel</em>]  Parallel computation.
<P>

<li>[<em>Limitations of Computing</em>] Finite-state limitations.  Lower
bounds.  Incomputability.  Intractability and NP-completeness.   The
glitch phenomenon.
<P>
<li><a name = "final">Comprehensive final exam</a> (<b>Date of Final: Fri. May 10, 2-5 p.m.</b>).
</ol>

<b><h4><a name = "mailing_assignments">How to email assignments:</a></h4></b>
<b>Use the following scheme only:</b>
<listing>
    elm -saN cs60grad@muddcs.cs.hmc.edu < your-code
</listing>

where N is the assignment number and your-code is a file containing your
code.  <b>Do not, under any circumstances, mail
using PINE.  This MIME encodes the file and we can't use it easily.  </b>
</html>
